<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="generator" content="rustdoc">
    <meta name="description" content="Source to the Rust file `/home/fmp/.cargo/registry/src/github.com-1ecc6299db9ec823/aho-corasick-0.5.3/src/lib.rs`.">
    <meta name="keywords" content="rust, rustlang, rust-lang">

    <title>lib.rs.html -- source</title>

    <link rel="stylesheet" type="text/css" href="../../normalize.css">
    <link rel="stylesheet" type="text/css" href="../../rustdoc.css">
    <link rel="stylesheet" type="text/css" href="../../main.css">
    

    
    
</head>
<body class="rustdoc source">
    <!--[if lte IE 8]>
    <div class="warning">
        This old browser is unsupported and will most likely display funky
        things.
    </div>
    <![endif]-->

    

    <nav class="sidebar">
        
        
    </nav>

    <nav class="sub">
        <form class="search-form js-only">
            <div class="search-container">
                <input class="search-input" name="search"
                       autocomplete="off"
                       placeholder="Click or press ‘S’ to search, ‘?’ for more options…"
                       type="search">
            </div>
        </form>
    </nav>

    <section id='main' class="content"><pre class="line-numbers"><span id="1">  1</span>
<span id="2">  2</span>
<span id="3">  3</span>
<span id="4">  4</span>
<span id="5">  5</span>
<span id="6">  6</span>
<span id="7">  7</span>
<span id="8">  8</span>
<span id="9">  9</span>
<span id="10"> 10</span>
<span id="11"> 11</span>
<span id="12"> 12</span>
<span id="13"> 13</span>
<span id="14"> 14</span>
<span id="15"> 15</span>
<span id="16"> 16</span>
<span id="17"> 17</span>
<span id="18"> 18</span>
<span id="19"> 19</span>
<span id="20"> 20</span>
<span id="21"> 21</span>
<span id="22"> 22</span>
<span id="23"> 23</span>
<span id="24"> 24</span>
<span id="25"> 25</span>
<span id="26"> 26</span>
<span id="27"> 27</span>
<span id="28"> 28</span>
<span id="29"> 29</span>
<span id="30"> 30</span>
<span id="31"> 31</span>
<span id="32"> 32</span>
<span id="33"> 33</span>
<span id="34"> 34</span>
<span id="35"> 35</span>
<span id="36"> 36</span>
<span id="37"> 37</span>
<span id="38"> 38</span>
<span id="39"> 39</span>
<span id="40"> 40</span>
<span id="41"> 41</span>
<span id="42"> 42</span>
<span id="43"> 43</span>
<span id="44"> 44</span>
<span id="45"> 45</span>
<span id="46"> 46</span>
<span id="47"> 47</span>
<span id="48"> 48</span>
<span id="49"> 49</span>
<span id="50"> 50</span>
<span id="51"> 51</span>
<span id="52"> 52</span>
<span id="53"> 53</span>
<span id="54"> 54</span>
<span id="55"> 55</span>
<span id="56"> 56</span>
<span id="57"> 57</span>
<span id="58"> 58</span>
<span id="59"> 59</span>
<span id="60"> 60</span>
<span id="61"> 61</span>
<span id="62"> 62</span>
<span id="63"> 63</span>
<span id="64"> 64</span>
<span id="65"> 65</span>
<span id="66"> 66</span>
<span id="67"> 67</span>
<span id="68"> 68</span>
<span id="69"> 69</span>
<span id="70"> 70</span>
<span id="71"> 71</span>
<span id="72"> 72</span>
<span id="73"> 73</span>
<span id="74"> 74</span>
<span id="75"> 75</span>
<span id="76"> 76</span>
<span id="77"> 77</span>
<span id="78"> 78</span>
<span id="79"> 79</span>
<span id="80"> 80</span>
<span id="81"> 81</span>
<span id="82"> 82</span>
<span id="83"> 83</span>
<span id="84"> 84</span>
<span id="85"> 85</span>
<span id="86"> 86</span>
<span id="87"> 87</span>
<span id="88"> 88</span>
<span id="89"> 89</span>
<span id="90"> 90</span>
<span id="91"> 91</span>
<span id="92"> 92</span>
<span id="93"> 93</span>
<span id="94"> 94</span>
<span id="95"> 95</span>
<span id="96"> 96</span>
<span id="97"> 97</span>
<span id="98"> 98</span>
<span id="99"> 99</span>
<span id="100">100</span>
<span id="101">101</span>
<span id="102">102</span>
<span id="103">103</span>
<span id="104">104</span>
<span id="105">105</span>
<span id="106">106</span>
<span id="107">107</span>
<span id="108">108</span>
<span id="109">109</span>
<span id="110">110</span>
<span id="111">111</span>
<span id="112">112</span>
<span id="113">113</span>
<span id="114">114</span>
<span id="115">115</span>
<span id="116">116</span>
<span id="117">117</span>
<span id="118">118</span>
<span id="119">119</span>
<span id="120">120</span>
<span id="121">121</span>
<span id="122">122</span>
<span id="123">123</span>
<span id="124">124</span>
<span id="125">125</span>
<span id="126">126</span>
<span id="127">127</span>
<span id="128">128</span>
<span id="129">129</span>
<span id="130">130</span>
<span id="131">131</span>
<span id="132">132</span>
<span id="133">133</span>
<span id="134">134</span>
<span id="135">135</span>
<span id="136">136</span>
<span id="137">137</span>
<span id="138">138</span>
<span id="139">139</span>
<span id="140">140</span>
<span id="141">141</span>
<span id="142">142</span>
<span id="143">143</span>
<span id="144">144</span>
<span id="145">145</span>
<span id="146">146</span>
<span id="147">147</span>
<span id="148">148</span>
<span id="149">149</span>
<span id="150">150</span>
<span id="151">151</span>
<span id="152">152</span>
<span id="153">153</span>
<span id="154">154</span>
<span id="155">155</span>
<span id="156">156</span>
<span id="157">157</span>
<span id="158">158</span>
<span id="159">159</span>
<span id="160">160</span>
<span id="161">161</span>
<span id="162">162</span>
<span id="163">163</span>
<span id="164">164</span>
<span id="165">165</span>
<span id="166">166</span>
<span id="167">167</span>
<span id="168">168</span>
<span id="169">169</span>
<span id="170">170</span>
<span id="171">171</span>
<span id="172">172</span>
<span id="173">173</span>
<span id="174">174</span>
<span id="175">175</span>
<span id="176">176</span>
<span id="177">177</span>
<span id="178">178</span>
<span id="179">179</span>
<span id="180">180</span>
<span id="181">181</span>
<span id="182">182</span>
<span id="183">183</span>
<span id="184">184</span>
<span id="185">185</span>
<span id="186">186</span>
<span id="187">187</span>
<span id="188">188</span>
<span id="189">189</span>
<span id="190">190</span>
<span id="191">191</span>
<span id="192">192</span>
<span id="193">193</span>
<span id="194">194</span>
<span id="195">195</span>
<span id="196">196</span>
<span id="197">197</span>
<span id="198">198</span>
<span id="199">199</span>
<span id="200">200</span>
<span id="201">201</span>
<span id="202">202</span>
<span id="203">203</span>
<span id="204">204</span>
<span id="205">205</span>
<span id="206">206</span>
<span id="207">207</span>
<span id="208">208</span>
<span id="209">209</span>
<span id="210">210</span>
<span id="211">211</span>
<span id="212">212</span>
<span id="213">213</span>
<span id="214">214</span>
<span id="215">215</span>
<span id="216">216</span>
<span id="217">217</span>
<span id="218">218</span>
<span id="219">219</span>
<span id="220">220</span>
<span id="221">221</span>
<span id="222">222</span>
<span id="223">223</span>
<span id="224">224</span>
<span id="225">225</span>
<span id="226">226</span>
<span id="227">227</span>
<span id="228">228</span>
<span id="229">229</span>
<span id="230">230</span>
<span id="231">231</span>
<span id="232">232</span>
<span id="233">233</span>
<span id="234">234</span>
<span id="235">235</span>
<span id="236">236</span>
<span id="237">237</span>
<span id="238">238</span>
<span id="239">239</span>
<span id="240">240</span>
<span id="241">241</span>
<span id="242">242</span>
<span id="243">243</span>
<span id="244">244</span>
<span id="245">245</span>
<span id="246">246</span>
<span id="247">247</span>
<span id="248">248</span>
<span id="249">249</span>
<span id="250">250</span>
<span id="251">251</span>
<span id="252">252</span>
<span id="253">253</span>
<span id="254">254</span>
<span id="255">255</span>
<span id="256">256</span>
<span id="257">257</span>
<span id="258">258</span>
<span id="259">259</span>
<span id="260">260</span>
<span id="261">261</span>
<span id="262">262</span>
<span id="263">263</span>
<span id="264">264</span>
<span id="265">265</span>
<span id="266">266</span>
<span id="267">267</span>
<span id="268">268</span>
<span id="269">269</span>
<span id="270">270</span>
<span id="271">271</span>
<span id="272">272</span>
<span id="273">273</span>
<span id="274">274</span>
<span id="275">275</span>
<span id="276">276</span>
<span id="277">277</span>
<span id="278">278</span>
<span id="279">279</span>
<span id="280">280</span>
<span id="281">281</span>
<span id="282">282</span>
<span id="283">283</span>
<span id="284">284</span>
<span id="285">285</span>
<span id="286">286</span>
<span id="287">287</span>
<span id="288">288</span>
<span id="289">289</span>
<span id="290">290</span>
<span id="291">291</span>
<span id="292">292</span>
<span id="293">293</span>
<span id="294">294</span>
<span id="295">295</span>
<span id="296">296</span>
<span id="297">297</span>
<span id="298">298</span>
<span id="299">299</span>
<span id="300">300</span>
<span id="301">301</span>
<span id="302">302</span>
<span id="303">303</span>
<span id="304">304</span>
<span id="305">305</span>
<span id="306">306</span>
<span id="307">307</span>
<span id="308">308</span>
<span id="309">309</span>
<span id="310">310</span>
<span id="311">311</span>
<span id="312">312</span>
<span id="313">313</span>
<span id="314">314</span>
<span id="315">315</span>
<span id="316">316</span>
<span id="317">317</span>
<span id="318">318</span>
<span id="319">319</span>
<span id="320">320</span>
<span id="321">321</span>
<span id="322">322</span>
<span id="323">323</span>
<span id="324">324</span>
<span id="325">325</span>
<span id="326">326</span>
<span id="327">327</span>
<span id="328">328</span>
<span id="329">329</span>
<span id="330">330</span>
<span id="331">331</span>
<span id="332">332</span>
<span id="333">333</span>
<span id="334">334</span>
<span id="335">335</span>
<span id="336">336</span>
<span id="337">337</span>
<span id="338">338</span>
<span id="339">339</span>
<span id="340">340</span>
<span id="341">341</span>
<span id="342">342</span>
<span id="343">343</span>
<span id="344">344</span>
<span id="345">345</span>
<span id="346">346</span>
<span id="347">347</span>
<span id="348">348</span>
<span id="349">349</span>
<span id="350">350</span>
<span id="351">351</span>
<span id="352">352</span>
<span id="353">353</span>
<span id="354">354</span>
<span id="355">355</span>
<span id="356">356</span>
<span id="357">357</span>
<span id="358">358</span>
<span id="359">359</span>
<span id="360">360</span>
<span id="361">361</span>
<span id="362">362</span>
<span id="363">363</span>
<span id="364">364</span>
<span id="365">365</span>
<span id="366">366</span>
<span id="367">367</span>
<span id="368">368</span>
<span id="369">369</span>
<span id="370">370</span>
<span id="371">371</span>
<span id="372">372</span>
<span id="373">373</span>
<span id="374">374</span>
<span id="375">375</span>
<span id="376">376</span>
<span id="377">377</span>
<span id="378">378</span>
<span id="379">379</span>
<span id="380">380</span>
<span id="381">381</span>
<span id="382">382</span>
<span id="383">383</span>
<span id="384">384</span>
<span id="385">385</span>
<span id="386">386</span>
<span id="387">387</span>
<span id="388">388</span>
<span id="389">389</span>
<span id="390">390</span>
<span id="391">391</span>
<span id="392">392</span>
<span id="393">393</span>
<span id="394">394</span>
<span id="395">395</span>
<span id="396">396</span>
<span id="397">397</span>
<span id="398">398</span>
<span id="399">399</span>
<span id="400">400</span>
<span id="401">401</span>
<span id="402">402</span>
<span id="403">403</span>
<span id="404">404</span>
<span id="405">405</span>
<span id="406">406</span>
<span id="407">407</span>
<span id="408">408</span>
<span id="409">409</span>
<span id="410">410</span>
<span id="411">411</span>
<span id="412">412</span>
<span id="413">413</span>
<span id="414">414</span>
<span id="415">415</span>
<span id="416">416</span>
<span id="417">417</span>
<span id="418">418</span>
<span id="419">419</span>
<span id="420">420</span>
<span id="421">421</span>
<span id="422">422</span>
<span id="423">423</span>
<span id="424">424</span>
<span id="425">425</span>
<span id="426">426</span>
<span id="427">427</span>
<span id="428">428</span>
<span id="429">429</span>
<span id="430">430</span>
<span id="431">431</span>
<span id="432">432</span>
<span id="433">433</span>
<span id="434">434</span>
<span id="435">435</span>
<span id="436">436</span>
<span id="437">437</span>
<span id="438">438</span>
<span id="439">439</span>
<span id="440">440</span>
<span id="441">441</span>
<span id="442">442</span>
<span id="443">443</span>
<span id="444">444</span>
<span id="445">445</span>
<span id="446">446</span>
<span id="447">447</span>
<span id="448">448</span>
<span id="449">449</span>
<span id="450">450</span>
<span id="451">451</span>
<span id="452">452</span>
<span id="453">453</span>
<span id="454">454</span>
<span id="455">455</span>
<span id="456">456</span>
<span id="457">457</span>
<span id="458">458</span>
<span id="459">459</span>
<span id="460">460</span>
<span id="461">461</span>
<span id="462">462</span>
<span id="463">463</span>
<span id="464">464</span>
<span id="465">465</span>
<span id="466">466</span>
<span id="467">467</span>
<span id="468">468</span>
<span id="469">469</span>
<span id="470">470</span>
<span id="471">471</span>
<span id="472">472</span>
<span id="473">473</span>
<span id="474">474</span>
<span id="475">475</span>
<span id="476">476</span>
<span id="477">477</span>
<span id="478">478</span>
<span id="479">479</span>
<span id="480">480</span>
<span id="481">481</span>
<span id="482">482</span>
<span id="483">483</span>
<span id="484">484</span>
<span id="485">485</span>
<span id="486">486</span>
<span id="487">487</span>
<span id="488">488</span>
<span id="489">489</span>
<span id="490">490</span>
<span id="491">491</span>
<span id="492">492</span>
<span id="493">493</span>
<span id="494">494</span>
<span id="495">495</span>
<span id="496">496</span>
<span id="497">497</span>
<span id="498">498</span>
<span id="499">499</span>
<span id="500">500</span>
<span id="501">501</span>
<span id="502">502</span>
<span id="503">503</span>
<span id="504">504</span>
<span id="505">505</span>
<span id="506">506</span>
<span id="507">507</span>
<span id="508">508</span>
<span id="509">509</span>
<span id="510">510</span>
<span id="511">511</span>
<span id="512">512</span>
<span id="513">513</span>
<span id="514">514</span>
<span id="515">515</span>
<span id="516">516</span>
<span id="517">517</span>
<span id="518">518</span>
<span id="519">519</span>
<span id="520">520</span>
<span id="521">521</span>
<span id="522">522</span>
<span id="523">523</span>
<span id="524">524</span>
<span id="525">525</span>
<span id="526">526</span>
<span id="527">527</span>
<span id="528">528</span>
<span id="529">529</span>
<span id="530">530</span>
<span id="531">531</span>
<span id="532">532</span>
<span id="533">533</span>
<span id="534">534</span>
<span id="535">535</span>
<span id="536">536</span>
<span id="537">537</span>
<span id="538">538</span>
<span id="539">539</span>
<span id="540">540</span>
<span id="541">541</span>
<span id="542">542</span>
<span id="543">543</span>
<span id="544">544</span>
<span id="545">545</span>
<span id="546">546</span>
<span id="547">547</span>
<span id="548">548</span>
<span id="549">549</span>
<span id="550">550</span>
<span id="551">551</span>
<span id="552">552</span>
<span id="553">553</span>
<span id="554">554</span>
<span id="555">555</span>
<span id="556">556</span>
<span id="557">557</span>
<span id="558">558</span>
<span id="559">559</span>
<span id="560">560</span>
<span id="561">561</span>
<span id="562">562</span>
<span id="563">563</span>
<span id="564">564</span>
<span id="565">565</span>
<span id="566">566</span>
<span id="567">567</span>
<span id="568">568</span>
<span id="569">569</span>
<span id="570">570</span>
<span id="571">571</span>
<span id="572">572</span>
<span id="573">573</span>
<span id="574">574</span>
<span id="575">575</span>
<span id="576">576</span>
<span id="577">577</span>
<span id="578">578</span>
<span id="579">579</span>
<span id="580">580</span>
<span id="581">581</span>
<span id="582">582</span>
<span id="583">583</span>
<span id="584">584</span>
<span id="585">585</span>
<span id="586">586</span>
<span id="587">587</span>
<span id="588">588</span>
<span id="589">589</span>
<span id="590">590</span>
<span id="591">591</span>
<span id="592">592</span>
<span id="593">593</span>
<span id="594">594</span>
<span id="595">595</span>
<span id="596">596</span>
<span id="597">597</span>
<span id="598">598</span>
<span id="599">599</span>
<span id="600">600</span>
<span id="601">601</span>
<span id="602">602</span>
<span id="603">603</span>
<span id="604">604</span>
<span id="605">605</span>
<span id="606">606</span>
<span id="607">607</span>
<span id="608">608</span>
<span id="609">609</span>
<span id="610">610</span>
<span id="611">611</span>
<span id="612">612</span>
<span id="613">613</span>
<span id="614">614</span>
<span id="615">615</span>
<span id="616">616</span>
<span id="617">617</span>
<span id="618">618</span>
<span id="619">619</span>
<span id="620">620</span>
<span id="621">621</span>
<span id="622">622</span>
<span id="623">623</span>
<span id="624">624</span>
<span id="625">625</span>
<span id="626">626</span>
<span id="627">627</span>
<span id="628">628</span>
<span id="629">629</span>
<span id="630">630</span>
<span id="631">631</span>
<span id="632">632</span>
<span id="633">633</span>
<span id="634">634</span>
<span id="635">635</span>
<span id="636">636</span>
<span id="637">637</span>
<span id="638">638</span>
<span id="639">639</span>
<span id="640">640</span>
<span id="641">641</span>
<span id="642">642</span>
<span id="643">643</span>
<span id="644">644</span>
<span id="645">645</span>
<span id="646">646</span>
<span id="647">647</span>
<span id="648">648</span>
<span id="649">649</span>
<span id="650">650</span>
<span id="651">651</span>
<span id="652">652</span>
<span id="653">653</span>
<span id="654">654</span>
<span id="655">655</span>
<span id="656">656</span>
<span id="657">657</span>
<span id="658">658</span>
<span id="659">659</span>
<span id="660">660</span>
<span id="661">661</span>
<span id="662">662</span>
<span id="663">663</span>
<span id="664">664</span>
<span id="665">665</span>
<span id="666">666</span>
<span id="667">667</span>
<span id="668">668</span>
<span id="669">669</span>
<span id="670">670</span>
<span id="671">671</span>
<span id="672">672</span>
<span id="673">673</span>
<span id="674">674</span>
<span id="675">675</span>
<span id="676">676</span>
<span id="677">677</span>
<span id="678">678</span>
<span id="679">679</span>
<span id="680">680</span>
<span id="681">681</span>
<span id="682">682</span>
<span id="683">683</span>
<span id="684">684</span>
<span id="685">685</span>
<span id="686">686</span>
<span id="687">687</span>
<span id="688">688</span>
<span id="689">689</span>
<span id="690">690</span>
<span id="691">691</span>
<span id="692">692</span>
<span id="693">693</span>
<span id="694">694</span>
<span id="695">695</span>
<span id="696">696</span>
<span id="697">697</span>
<span id="698">698</span>
<span id="699">699</span>
<span id="700">700</span>
<span id="701">701</span>
<span id="702">702</span>
<span id="703">703</span>
<span id="704">704</span>
<span id="705">705</span>
<span id="706">706</span>
<span id="707">707</span>
<span id="708">708</span>
<span id="709">709</span>
<span id="710">710</span>
<span id="711">711</span>
<span id="712">712</span>
<span id="713">713</span>
<span id="714">714</span>
<span id="715">715</span>
<span id="716">716</span>
<span id="717">717</span>
<span id="718">718</span>
<span id="719">719</span>
<span id="720">720</span>
<span id="721">721</span>
<span id="722">722</span>
<span id="723">723</span>
<span id="724">724</span>
<span id="725">725</span>
<span id="726">726</span>
<span id="727">727</span>
<span id="728">728</span>
<span id="729">729</span>
<span id="730">730</span>
<span id="731">731</span>
<span id="732">732</span>
<span id="733">733</span>
<span id="734">734</span>
<span id="735">735</span>
<span id="736">736</span>
<span id="737">737</span>
<span id="738">738</span>
<span id="739">739</span>
<span id="740">740</span>
<span id="741">741</span>
<span id="742">742</span>
<span id="743">743</span>
<span id="744">744</span>
<span id="745">745</span>
<span id="746">746</span>
<span id="747">747</span>
<span id="748">748</span>
<span id="749">749</span>
<span id="750">750</span>
<span id="751">751</span>
<span id="752">752</span>
<span id="753">753</span>
<span id="754">754</span>
<span id="755">755</span>
<span id="756">756</span>
<span id="757">757</span>
<span id="758">758</span>
<span id="759">759</span>
<span id="760">760</span>
<span id="761">761</span>
<span id="762">762</span>
<span id="763">763</span>
<span id="764">764</span>
<span id="765">765</span>
<span id="766">766</span>
<span id="767">767</span>
<span id="768">768</span>
<span id="769">769</span>
<span id="770">770</span>
<span id="771">771</span>
<span id="772">772</span>
<span id="773">773</span>
<span id="774">774</span>
<span id="775">775</span>
<span id="776">776</span>
<span id="777">777</span>
<span id="778">778</span>
<span id="779">779</span>
<span id="780">780</span>
<span id="781">781</span>
<span id="782">782</span>
<span id="783">783</span>
<span id="784">784</span>
<span id="785">785</span>
<span id="786">786</span>
<span id="787">787</span>
<span id="788">788</span>
<span id="789">789</span>
<span id="790">790</span>
<span id="791">791</span>
<span id="792">792</span>
<span id="793">793</span>
<span id="794">794</span>
<span id="795">795</span>
<span id="796">796</span>
<span id="797">797</span>
<span id="798">798</span>
<span id="799">799</span>
<span id="800">800</span>
<span id="801">801</span>
<span id="802">802</span>
<span id="803">803</span>
<span id="804">804</span>
<span id="805">805</span>
<span id="806">806</span>
<span id="807">807</span>
<span id="808">808</span>
<span id="809">809</span>
<span id="810">810</span>
<span id="811">811</span>
<span id="812">812</span>
<span id="813">813</span>
<span id="814">814</span>
<span id="815">815</span>
<span id="816">816</span>
<span id="817">817</span>
<span id="818">818</span>
<span id="819">819</span>
<span id="820">820</span>
<span id="821">821</span>
<span id="822">822</span>
<span id="823">823</span>
<span id="824">824</span>
<span id="825">825</span>
<span id="826">826</span>
<span id="827">827</span>
<span id="828">828</span>
<span id="829">829</span>
<span id="830">830</span>
<span id="831">831</span>
<span id="832">832</span>
<span id="833">833</span>
<span id="834">834</span>
<span id="835">835</span>
<span id="836">836</span>
<span id="837">837</span>
<span id="838">838</span>
<span id="839">839</span>
<span id="840">840</span>
<span id="841">841</span>
<span id="842">842</span>
<span id="843">843</span>
<span id="844">844</span>
<span id="845">845</span>
<span id="846">846</span>
<span id="847">847</span>
<span id="848">848</span>
<span id="849">849</span>
<span id="850">850</span>
<span id="851">851</span>
<span id="852">852</span>
<span id="853">853</span>
<span id="854">854</span>
<span id="855">855</span>
<span id="856">856</span>
<span id="857">857</span>
<span id="858">858</span>
<span id="859">859</span>
<span id="860">860</span>
<span id="861">861</span>
<span id="862">862</span>
<span id="863">863</span>
<span id="864">864</span>
<span id="865">865</span>
<span id="866">866</span>
<span id="867">867</span>
<span id="868">868</span>
<span id="869">869</span>
<span id="870">870</span>
<span id="871">871</span>
<span id="872">872</span>
<span id="873">873</span>
<span id="874">874</span>
<span id="875">875</span>
<span id="876">876</span>
<span id="877">877</span>
<span id="878">878</span>
<span id="879">879</span>
<span id="880">880</span>
<span id="881">881</span>
<span id="882">882</span>
<span id="883">883</span>
<span id="884">884</span>
<span id="885">885</span>
<span id="886">886</span>
<span id="887">887</span>
<span id="888">888</span>
<span id="889">889</span>
<span id="890">890</span>
<span id="891">891</span>
<span id="892">892</span>
<span id="893">893</span>
<span id="894">894</span>
<span id="895">895</span>
<span id="896">896</span>
<span id="897">897</span>
<span id="898">898</span>
<span id="899">899</span>
<span id="900">900</span>
<span id="901">901</span>
<span id="902">902</span>
<span id="903">903</span>
<span id="904">904</span>
<span id="905">905</span>
<span id="906">906</span>
<span id="907">907</span>
<span id="908">908</span>
<span id="909">909</span>
<span id="910">910</span>
<span id="911">911</span>
<span id="912">912</span>
<span id="913">913</span>
<span id="914">914</span>
<span id="915">915</span>
<span id="916">916</span>
<span id="917">917</span>
<span id="918">918</span>
<span id="919">919</span>
<span id="920">920</span>
<span id="921">921</span>
<span id="922">922</span>
<span id="923">923</span>
<span id="924">924</span>
<span id="925">925</span>
</pre><pre class="rust ">
<span class="doccomment">/*!
An implementation of the
[Aho-Corasick string search algorithm](https://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm).

The Aho-Corasick algorithm is principally useful when you need to search many
large texts for a fixed (possibly large) set of keywords. In particular, the
Aho-Corasick algorithm preprocesses the set of keywords by constructing a
finite state machine. The search phase is then a quick linear scan through the
text. Each character in the search text causes a state transition in the
automaton. Matches are reported when the automaton enters a match state.

# Examples

The main type exposed by this crate is `AcAutomaton`, which can be constructed
from an iterator of pattern strings:

```rust
use aho_corasick::{Automaton, AcAutomaton};

let aut = AcAutomaton::new(vec![&quot;apple&quot;, &quot;maple&quot;]);

// AcAutomaton also implements `FromIterator`:
let aut: AcAutomaton&lt;&amp;str&gt; = [&quot;apple&quot;, &quot;maple&quot;].iter().cloned().collect();
```

Finding matches can be done with `find`:

```rust
use aho_corasick::{Automaton, AcAutomaton, Match};

let aut = AcAutomaton::new(vec![&quot;apple&quot;, &quot;maple&quot;]);
let mut it = aut.find(&quot;I like maple apples.&quot;);
assert_eq!(it.next(), Some(Match {
    pati: 1,
    start: 7,
    end: 12,
}));
assert_eq!(it.next(), Some(Match {
    pati: 0,
    start: 13,
    end: 18,
}));
assert_eq!(it.next(), None);
```

Use `find_overlapping` if you want to report all matches, even if they
overlap with each other.

```rust
use aho_corasick::{Automaton, AcAutomaton, Match};

let aut = AcAutomaton::new(vec![&quot;abc&quot;, &quot;a&quot;]);
let matches: Vec&lt;_&gt; = aut.find_overlapping(&quot;abc&quot;).collect();
assert_eq!(matches, vec![
    Match { pati: 1, start: 0, end: 1}, Match { pati: 0, start: 0, end: 3 },
]);

// Regular `find` will report only one match:
let matches: Vec&lt;_&gt; = aut.find(&quot;abc&quot;).collect();
assert_eq!(matches, vec![Match { pati: 1, start: 0, end: 1}]);
```

Finally, there are also methods for finding matches on *streams*. Namely, the
search text does not have to live in memory. It&#39;s useful to run this on files
that can&#39;t fit into memory:

```no_run
use std::fs::File;

use aho_corasick::{Automaton, AcAutomaton};

let aut = AcAutomaton::new(vec![&quot;foo&quot;, &quot;bar&quot;, &quot;baz&quot;]);
let rdr = File::open(&quot;search.txt&quot;).unwrap();
for m in aut.stream_find(rdr) {
    let m = m.unwrap(); // could be an IO error
    println!(&quot;Pattern &#39;{}&#39; matched at: ({}, {})&quot;,
             aut.pattern(m.pati), m.start, m.end);
}
```

There is also `stream_find_overlapping`, which is just like `find_overlapping`,
but it operates on streams.

Please see `dict-search.rs` in this crate&#39;s `examples` directory for a more
complete example. It creates a large automaton from a dictionary and can do a
streaming match over arbitrarily large data.

# Memory usage

A key aspect of an Aho-Corasick implementation is how the state transitions
are represented. The easiest way to make the automaton fast is to store a
sparse 256-slot map in each state. It maps an input byte to a state index.
This makes the matching loop extremely fast, since it translates to a simple
pointer read.

The problem is that as the automaton accumulates more states, you end up paying
a `256 * 4` (`4` is for the `u32` state index) byte penalty for every state
regardless of how many transitions it has.

To solve this, only states near the root of the automaton have this sparse
map representation. States near the leaves of the automaton use a dense mapping
that requires a linear scan.

(The specific limit currently set is `3`, so that states with a depth less than
or equal to `3` are less memory efficient. The result is that the memory usage
of the automaton stops growing rapidly past ~60MB, even for automatons with
thousands of patterns.)

If you&#39;d like to opt for the less-memory-efficient-but-faster version, then
you can construct an `AcAutomaton` with a `Sparse` transition strategy:

```rust
use aho_corasick::{Automaton, AcAutomaton, Match, Sparse};

let aut = AcAutomaton::&lt;&amp;str, Sparse&gt;::with_transitions(vec![&quot;abc&quot;, &quot;a&quot;]);
let matches: Vec&lt;_&gt; = aut.find(&quot;abc&quot;).collect();
assert_eq!(matches, vec![Match { pati: 1, start: 0, end: 1}]);
```
*/</span>

<span class="attribute">#<span class="op">!</span>[<span class="ident">deny</span>(<span class="ident">missing_docs</span>)]</span>

<span class="kw">extern</span> <span class="kw">crate</span> <span class="ident">memchr</span>;
<span class="attribute">#[<span class="ident">cfg</span>(<span class="ident">test</span>)]</span> <span class="kw">extern</span> <span class="kw">crate</span> <span class="ident">quickcheck</span>;
<span class="attribute">#[<span class="ident">cfg</span>(<span class="ident">test</span>)]</span> <span class="kw">extern</span> <span class="kw">crate</span> <span class="ident">rand</span>;

<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">collections</span>::<span class="ident">VecDeque</span>;
<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">fmt</span>;
<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">iter</span>::<span class="ident">FromIterator</span>;
<span class="kw">use</span> <span class="ident">std</span>::<span class="ident">mem</span>;

<span class="kw">pub</span> <span class="kw">use</span> <span class="self">self</span>::<span class="ident">autiter</span>::{
    <span class="ident">Automaton</span>, <span class="ident">Match</span>,
    <span class="ident">Matches</span>, <span class="ident">MatchesOverlapping</span>, <span class="ident">StreamMatches</span>, <span class="ident">StreamMatchesOverlapping</span>,
};
<span class="kw">pub</span> <span class="kw">use</span> <span class="self">self</span>::<span class="ident">full</span>::<span class="ident">FullAcAutomaton</span>;

<span class="comment">// We&#39;re specifying paths explicitly so that we can use</span>
<span class="comment">// these modules simultaneously from `main.rs`.</span>
<span class="comment">// Should probably make just make `main.rs` a separate crate.</span>
<span class="attribute">#[<span class="ident">path</span> <span class="op">=</span> <span class="string">&quot;autiter.rs&quot;</span>]</span>
<span class="kw">mod</span> <span class="ident">autiter</span>;
<span class="attribute">#[<span class="ident">path</span> <span class="op">=</span> <span class="string">&quot;full.rs&quot;</span>]</span>
<span class="kw">mod</span> <span class="ident">full</span>;

<span class="doccomment">/// The integer type used for the state index.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// Limiting this to 32 bit integers can have a big impact on memory usage</span>
<span class="doccomment">/// when using the `Sparse` transition representation.</span>
<span class="kw">pub</span> <span class="kw">type</span> <span class="ident">StateIdx</span> <span class="op">=</span> <span class="ident">u32</span>;

<span class="comment">// Constants for special state indexes.</span>
<span class="kw">const</span> <span class="ident">FAIL_STATE</span>: <span class="ident">u32</span> <span class="op">=</span> <span class="number">0</span>;
<span class="kw">const</span> <span class="ident">ROOT_STATE</span>: <span class="ident">u32</span> <span class="op">=</span> <span class="number">1</span>;

<span class="comment">// Limit the depth at which we use a sparse alphabet map. Once the limit is</span>
<span class="comment">// reached, a dense set is used (and lookup becomes O(n)).</span>
<span class="comment">//</span>
<span class="comment">// This does have a performance hit, but the (straight forward) alternative</span>
<span class="comment">// is to have a `256 * 4` byte overhead for every state.</span>
<span class="comment">// Given that Aho-Corasick is typically used for dictionary searching, this</span>
<span class="comment">// can lead to dramatic memory bloat.</span>
<span class="comment">//</span>
<span class="comment">// This limit should only be increased at your peril. Namely, in the worst</span>
<span class="comment">// case, `256^DENSE_DEPTH_THRESHOLD * 4` corresponds to the memory usage in</span>
<span class="comment">// bytes. A value of `1` gives us a good balance. This is also a happy point</span>
<span class="comment">// in the benchmarks. A value of `0` gives considerably worse times on certain</span>
<span class="comment">// benchmarks (e.g., `ac_ten_one_prefix_byte_every_match`) than even a value</span>
<span class="comment">// of `1`. A value of `2` is slightly better than `1` and it looks like gains</span>
<span class="comment">// level off at that point with not much observable difference when set to</span>
<span class="comment">// `3`.</span>
<span class="comment">//</span>
<span class="comment">// Why not make this user configurable? Well, it doesn&#39;t make much sense</span>
<span class="comment">// because we pay for it with case analysis in the matching loop. Increasing it</span>
<span class="comment">// doesn&#39;t have much impact on performance (outside of pathological cases?).</span>
<span class="comment">//</span>
<span class="comment">// N.B. Someone else seems to have discovered an alternative, but I haven&#39;t</span>
<span class="comment">// grokked it yet: https://github.com/mischasan/aho-corasick</span>
<span class="kw">const</span> <span class="ident">DENSE_DEPTH_THRESHOLD</span>: <span class="ident">u32</span> <span class="op">=</span> <span class="number">1</span>;

<span class="doccomment">/// An Aho-Corasick finite automaton.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// The type parameter `P` is the type of the pattern that was used to</span>
<span class="doccomment">/// construct this AcAutomaton.</span>
<span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>)]</span>
<span class="kw">pub</span> <span class="kw">struct</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">=</span><span class="ident">Dense</span><span class="op">&gt;</span> {
    <span class="ident">pats</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span>,
    <span class="ident">states</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;&gt;</span>,
    <span class="ident">start_bytes</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">u8</span><span class="op">&gt;</span>,
}

<span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>)]</span>
<span class="kw">struct</span> <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="ident">out</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">usize</span><span class="op">&gt;</span>,
    <span class="ident">fail</span>: <span class="ident">StateIdx</span>,
    <span class="ident">goto</span>: <span class="ident">T</span>,
    <span class="ident">depth</span>: <span class="ident">u32</span>,
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">P</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span> {
    <span class="doccomment">/// Create a new automaton from an iterator of patterns.</span>
    <span class="doccomment">///</span>
    <span class="doccomment">/// The patterns must be convertible to bytes (`&amp;[u8]`) via the `AsRef`</span>
    <span class="doccomment">/// trait.</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">new</span><span class="op">&lt;</span><span class="ident">I</span><span class="op">&gt;</span>(<span class="ident">pats</span>: <span class="ident">I</span>) <span class="op">-&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">Dense</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">I</span>: <span class="ident">IntoIterator</span><span class="op">&lt;</span><span class="ident">Item</span><span class="op">=</span><span class="ident">P</span><span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">with_transitions</span>(<span class="ident">pats</span>)
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">P</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span>, <span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
    <span class="doccomment">/// Create a new automaton from an iterator of patterns.</span>
    <span class="doccomment">///</span>
    <span class="doccomment">/// This constructor allows one to choose the transition representation.</span>
    <span class="doccomment">///</span>
    <span class="doccomment">/// The patterns must be convertible to bytes (`&amp;[u8]`) via the `AsRef`</span>
    <span class="doccomment">/// trait.</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">with_transitions</span><span class="op">&lt;</span><span class="ident">I</span><span class="op">&gt;</span>(<span class="ident">pats</span>: <span class="ident">I</span>) <span class="op">-&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">I</span>: <span class="ident">IntoIterator</span><span class="op">&lt;</span><span class="ident">Item</span><span class="op">=</span><span class="ident">P</span><span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span> {
            <span class="ident">pats</span>: <span class="macro">vec</span><span class="macro">!</span>[], <span class="comment">// filled in later, avoid wrath of borrow checker</span>
            <span class="ident">states</span>: <span class="macro">vec</span><span class="macro">!</span>[<span class="ident">State</span>::<span class="ident">new</span>(<span class="number">0</span>), <span class="ident">State</span>::<span class="ident">new</span>(<span class="number">0</span>)], <span class="comment">// empty and root</span>
            <span class="ident">start_bytes</span>: <span class="macro">vec</span><span class="macro">!</span>[], <span class="comment">// also filled in later</span>
        }.<span class="ident">build</span>(<span class="ident">pats</span>.<span class="ident">into_iter</span>().<span class="ident">collect</span>())
    }

    <span class="doccomment">/// Build out the entire automaton into a single matrix.</span>
    <span class="doccomment">///</span>
    <span class="doccomment">/// This will make searching as fast as possible at the expense of using</span>
    <span class="doccomment">/// at least `4 * 256 * #states` bytes of memory.</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">into_full</span>(<span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">FullAcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span> {
        <span class="ident">FullAcAutomaton</span>::<span class="ident">new</span>(<span class="self">self</span>)
    }

    <span class="attribute">#[<span class="ident">doc</span>(<span class="ident">hidden</span>)]</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">num_states</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span> {
        <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">len</span>()
    }

    <span class="attribute">#[<span class="ident">doc</span>(<span class="ident">hidden</span>)]</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">heap_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span> {
        <span class="self">self</span>.<span class="ident">pats</span>.<span class="ident">iter</span>()
            .<span class="ident">map</span>(<span class="op">|</span><span class="ident">p</span><span class="op">|</span> <span class="ident">mem</span>::<span class="ident">size_of</span>::<span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span>() <span class="op">+</span> <span class="ident">p</span>.<span class="ident">as_ref</span>().<span class="ident">len</span>())
            .<span class="ident">fold</span>(<span class="number">0</span>, <span class="op">|</span><span class="ident">a</span>, <span class="ident">b</span><span class="op">|</span> <span class="ident">a</span> <span class="op">+</span> <span class="ident">b</span>)
        <span class="op">+</span> <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">iter</span>()
              .<span class="ident">map</span>(<span class="op">|</span><span class="ident">s</span><span class="op">|</span> <span class="ident">mem</span>::<span class="ident">size_of</span>::<span class="op">&lt;</span><span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;&gt;</span>() <span class="op">+</span> <span class="ident">s</span>.<span class="ident">heap_bytes</span>())
              .<span class="ident">fold</span>(<span class="number">0</span>, <span class="op">|</span><span class="ident">a</span>, <span class="ident">b</span><span class="op">|</span> <span class="ident">a</span> <span class="op">+</span> <span class="ident">b</span>)
        <span class="op">+</span> <span class="self">self</span>.<span class="ident">start_bytes</span>.<span class="ident">len</span>()
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">P</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span>, <span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">Automaton</span><span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span> <span class="kw">for</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">next_state</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="kw-2">mut</span> <span class="ident">si</span>: <span class="ident">StateIdx</span>, <span class="ident">b</span>: <span class="ident">u8</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span> {
        <span class="kw">loop</span> {
            <span class="kw">let</span> <span class="ident">maybe_si</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">b</span>);
            <span class="kw">if</span> <span class="ident">maybe_si</span> <span class="op">!=</span> <span class="ident">FAIL_STATE</span> {
                <span class="ident">si</span> <span class="op">=</span> <span class="ident">maybe_si</span>;
                <span class="kw">break</span>;
            } <span class="kw">else</span> {
                <span class="ident">si</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">fail</span>;
            }
        }
        <span class="ident">si</span>
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">get_match</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>, <span class="ident">outi</span>: <span class="ident">usize</span>, <span class="ident">texti</span>: <span class="ident">usize</span>) <span class="op">-&gt;</span> <span class="ident">Match</span> {
        <span class="kw">let</span> <span class="ident">pati</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">out</span>[<span class="ident">outi</span>];
        <span class="kw">let</span> <span class="ident">patlen</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">pats</span>[<span class="ident">pati</span>].<span class="ident">as_ref</span>().<span class="ident">len</span>();
        <span class="kw">let</span> <span class="ident">start</span> <span class="op">=</span> <span class="ident">texti</span> <span class="op">+</span> <span class="number">1</span> <span class="op">-</span> <span class="ident">patlen</span>;
        <span class="ident">Match</span> {
            <span class="ident">pati</span>: <span class="ident">pati</span>,
            <span class="ident">start</span>: <span class="ident">start</span>,
            <span class="ident">end</span>: <span class="ident">start</span> <span class="op">+</span> <span class="ident">patlen</span>,
        }
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">has_match</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>, <span class="ident">outi</span>: <span class="ident">usize</span>) <span class="op">-&gt;</span> <span class="ident">bool</span> {
        <span class="ident">outi</span> <span class="op">&lt;</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">out</span>.<span class="ident">len</span>()
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">start_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="kw-2">&amp;</span>[<span class="ident">u8</span>] {
        <span class="kw-2">&amp;</span><span class="self">self</span>.<span class="ident">start_bytes</span>
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">patterns</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="kw-2">&amp;</span>[<span class="ident">P</span>] {
        <span class="kw-2">&amp;</span><span class="self">self</span>.<span class="ident">pats</span>
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">pattern</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">i</span>: <span class="ident">usize</span>) <span class="op">-&gt;</span> <span class="kw-2">&amp;</span><span class="ident">P</span> {
        <span class="kw-2">&amp;</span><span class="self">self</span>.<span class="ident">pats</span>[<span class="ident">i</span>]
    }
}

<span class="comment">// Below contains code for *building* the automaton. It&#39;s a reasonably faithful</span>
<span class="comment">// translation of the description/psuedo-code from:</span>
<span class="comment">// http://www.cs.uku.fi/~kilpelai/BSA05/lectures/slides04.pdf</span>

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">P</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span>, <span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
    <span class="comment">// This is the first phase and builds the initial keyword tree.</span>
    <span class="kw">fn</span> <span class="ident">build</span>(<span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">pats</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">P</span><span class="op">&gt;</span>) <span class="op">-&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
        <span class="kw">for</span> (<span class="ident">pati</span>, <span class="ident">pat</span>) <span class="kw">in</span> <span class="ident">pats</span>.<span class="ident">iter</span>().<span class="ident">enumerate</span>() {
            <span class="kw">if</span> <span class="ident">pat</span>.<span class="ident">as_ref</span>().<span class="ident">is_empty</span>() {
                <span class="kw">continue</span>;
            }
            <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">previ</span> <span class="op">=</span> <span class="ident">ROOT_STATE</span>;
            <span class="kw">for</span> <span class="kw-2">&amp;</span><span class="ident">b</span> <span class="kw">in</span> <span class="ident">pat</span>.<span class="ident">as_ref</span>() {
                <span class="kw">if</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">previ</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">b</span>) <span class="op">!=</span> <span class="ident">FAIL_STATE</span> {
                    <span class="ident">previ</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">previ</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">b</span>);
                } <span class="kw">else</span> {
                    <span class="kw">let</span> <span class="ident">depth</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">previ</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">depth</span> <span class="op">+</span> <span class="number">1</span>;
                    <span class="kw">let</span> <span class="ident">nexti</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">add_state</span>(<span class="ident">State</span>::<span class="ident">new</span>(<span class="ident">depth</span>));
                    <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">previ</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">set_goto</span>(<span class="ident">b</span>, <span class="ident">nexti</span>);
                    <span class="ident">previ</span> <span class="op">=</span> <span class="ident">nexti</span>;
                }
            }
            <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">previ</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">out</span>.<span class="ident">push</span>(<span class="ident">pati</span>);
        }
        <span class="kw">for</span> <span class="ident">c</span> <span class="kw">in</span> (<span class="number">0</span>..<span class="number">256</span>).<span class="ident">into_iter</span>().<span class="ident">map</span>(<span class="op">|</span><span class="ident">c</span><span class="op">|</span> <span class="ident">c</span> <span class="kw">as</span> <span class="ident">u8</span>) {
            <span class="kw">if</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">ROOT_STATE</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">c</span>) <span class="op">==</span> <span class="ident">FAIL_STATE</span> {
                <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">ROOT_STATE</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">set_goto</span>(<span class="ident">c</span>, <span class="ident">ROOT_STATE</span>);
            } <span class="kw">else</span> {
                <span class="self">self</span>.<span class="ident">start_bytes</span>.<span class="ident">push</span>(<span class="ident">c</span>);
            }
        }
        <span class="comment">// If any of the start bytes are non-ASCII, then remove them all,</span>
        <span class="comment">// because we don&#39;t want to be calling memchr on non-ASCII bytes.</span>
        <span class="comment">// (Well, we could, but it requires being more clever. Simply using</span>
        <span class="comment">// the prefix byte isn&#39;t good enough.)</span>
        <span class="kw">if</span> <span class="self">self</span>.<span class="ident">start_bytes</span>.<span class="ident">iter</span>().<span class="ident">any</span>(<span class="op">|</span><span class="kw-2">&amp;</span><span class="ident">b</span><span class="op">|</span> <span class="ident">b</span> <span class="op">&gt;</span> <span class="number">0x7F</span>) {
            <span class="self">self</span>.<span class="ident">start_bytes</span>.<span class="ident">clear</span>();
        }
        <span class="self">self</span>.<span class="ident">pats</span> <span class="op">=</span> <span class="ident">pats</span>;
        <span class="self">self</span>.<span class="ident">fill</span>()
    }

    <span class="comment">// The second phase that fills in the back links.</span>
    <span class="kw">fn</span> <span class="ident">fill</span>(<span class="kw-2">mut</span> <span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
        <span class="comment">// Fill up the queue with all non-root transitions out of the root</span>
        <span class="comment">// node. Then proceed by breadth first traversal.</span>
        <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">q</span> <span class="op">=</span> <span class="ident">VecDeque</span>::<span class="ident">new</span>();
        <span class="kw">for</span> <span class="ident">c</span> <span class="kw">in</span> (<span class="number">0</span>..<span class="number">256</span>).<span class="ident">into_iter</span>().<span class="ident">map</span>(<span class="op">|</span><span class="ident">c</span><span class="op">|</span> <span class="ident">c</span> <span class="kw">as</span> <span class="ident">u8</span>) {
            <span class="kw">let</span> <span class="ident">si</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">ROOT_STATE</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">c</span>);
            <span class="kw">if</span> <span class="ident">si</span> <span class="op">!=</span> <span class="ident">ROOT_STATE</span> {
                <span class="ident">q</span>.<span class="ident">push_front</span>(<span class="ident">si</span>);
            }
        }
        <span class="kw">while</span> <span class="kw">let</span> <span class="prelude-val">Some</span>(<span class="ident">si</span>) <span class="op">=</span> <span class="ident">q</span>.<span class="ident">pop_back</span>() {
            <span class="kw">for</span> <span class="ident">c</span> <span class="kw">in</span> (<span class="number">0</span>..<span class="number">256</span>).<span class="ident">into_iter</span>().<span class="ident">map</span>(<span class="op">|</span><span class="ident">c</span><span class="op">|</span> <span class="ident">c</span> <span class="kw">as</span> <span class="ident">u8</span>) {
                <span class="kw">let</span> <span class="ident">u</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">c</span>);
                <span class="kw">if</span> <span class="ident">u</span> <span class="op">!=</span> <span class="ident">FAIL_STATE</span> {
                    <span class="ident">q</span>.<span class="ident">push_front</span>(<span class="ident">u</span>);
                    <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">v</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">si</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">fail</span>;
                    <span class="kw">while</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">v</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">c</span>) <span class="op">==</span> <span class="ident">FAIL_STATE</span> {
                        <span class="ident">v</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">v</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">fail</span>;
                    }
                    <span class="kw">let</span> <span class="ident">ufail</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">v</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">goto</span>(<span class="ident">c</span>);
                    <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">u</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">fail</span> <span class="op">=</span> <span class="ident">ufail</span>;
                    <span class="kw">let</span> <span class="ident">ufail_out</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">ufail</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">out</span>.<span class="ident">clone</span>();
                    <span class="self">self</span>.<span class="ident">states</span>[<span class="ident">u</span> <span class="kw">as</span> <span class="ident">usize</span>].<span class="ident">out</span>.<span class="ident">extend</span>(<span class="ident">ufail_out</span>);
                }
            }
        }
        <span class="self">self</span>
    }

    <span class="kw">fn</span> <span class="ident">add_state</span>(<span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">state</span>: <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span> {
        <span class="kw">let</span> <span class="ident">i</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">len</span>();
        <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">push</span>(<span class="ident">state</span>);
        <span class="ident">i</span> <span class="kw">as</span> <span class="ident">StateIdx</span>
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="kw">fn</span> <span class="ident">new</span>(<span class="ident">depth</span>: <span class="ident">u32</span>) <span class="op">-&gt;</span> <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
        <span class="ident">State</span> {
            <span class="ident">out</span>: <span class="macro">vec</span><span class="macro">!</span>[],
            <span class="ident">fail</span>: <span class="number">1</span>,
            <span class="ident">goto</span>: <span class="ident">Transitions</span>::<span class="ident">new</span>(<span class="ident">depth</span>),
            <span class="ident">depth</span>: <span class="ident">depth</span>,
        }
    }

    <span class="kw">fn</span> <span class="ident">goto</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">b</span>: <span class="ident">u8</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span> {
        <span class="self">self</span>.<span class="ident">goto</span>.<span class="ident">goto</span>(<span class="ident">b</span>)
    }

    <span class="kw">fn</span> <span class="ident">set_goto</span>(<span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">b</span>: <span class="ident">u8</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>) {
        <span class="self">self</span>.<span class="ident">goto</span>.<span class="ident">set_goto</span>(<span class="ident">b</span>, <span class="ident">si</span>);
    }

    <span class="kw">fn</span> <span class="ident">heap_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span> {
        (<span class="self">self</span>.<span class="ident">out</span>.<span class="ident">len</span>() <span class="op">*</span> <span class="ident">usize_bytes</span>())
        <span class="op">+</span> <span class="self">self</span>.<span class="ident">goto</span>.<span class="ident">heap_bytes</span>()
    }
}

<span class="doccomment">/// An abstraction over state transition strategies.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// This is an attempt to let the caller choose the space/time trade offs</span>
<span class="doccomment">/// used for state transitions.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// (It&#39;s possible that this interface is merely good enough for just the two</span>
<span class="doccomment">/// implementations in this crate.)</span>
<span class="kw">pub</span> <span class="kw">trait</span> <span class="ident">Transitions</span> {
    <span class="doccomment">/// Return a new state at the given depth.</span>
    <span class="kw">fn</span> <span class="ident">new</span>(<span class="ident">depth</span>: <span class="ident">u32</span>) <span class="op">-&gt;</span> <span class="self">Self</span>;
    <span class="doccomment">/// Return the next state index given the next character.</span>
    <span class="kw">fn</span> <span class="ident">goto</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">alpha</span>: <span class="ident">u8</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span>;
    <span class="doccomment">/// Set the next state index for the character given.</span>
    <span class="kw">fn</span> <span class="ident">set_goto</span>(<span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">alpha</span>: <span class="ident">u8</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>);
    <span class="doccomment">/// The memory use in bytes (on the heap) of this set of transitions.</span>
    <span class="kw">fn</span> <span class="ident">heap_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span>;
}

<span class="doccomment">/// State transitions that can be stored either sparsely or densely.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// This uses less space but at the expense of slower matching.</span>
<span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>, <span class="ident">Debug</span>)]</span>
<span class="kw">pub</span> <span class="kw">struct</span> <span class="ident">Dense</span>(<span class="ident">DenseChoice</span>);

<span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>, <span class="ident">Debug</span>)]</span>
<span class="kw">enum</span> <span class="ident">DenseChoice</span> {
    <span class="ident">Sparse</span>(<span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">StateIdx</span><span class="op">&gt;</span>), <span class="comment">// indexed by alphabet</span>
    <span class="ident">Dense</span>(<span class="ident">Vec</span><span class="op">&lt;</span>(<span class="ident">u8</span>, <span class="ident">StateIdx</span>)<span class="op">&gt;</span>),
}

<span class="kw">impl</span> <span class="ident">Transitions</span> <span class="kw">for</span> <span class="ident">Dense</span> {
    <span class="kw">fn</span> <span class="ident">new</span>(<span class="ident">depth</span>: <span class="ident">u32</span>) <span class="op">-&gt;</span> <span class="ident">Dense</span> {
        <span class="kw">if</span> <span class="ident">depth</span> <span class="op">&lt;=</span> <span class="ident">DENSE_DEPTH_THRESHOLD</span> {
            <span class="ident">Dense</span>(<span class="ident">DenseChoice</span>::<span class="ident">Sparse</span>(<span class="macro">vec</span><span class="macro">!</span>[<span class="number">0</span>; <span class="number">256</span>]))
        } <span class="kw">else</span> {
            <span class="ident">Dense</span>(<span class="ident">DenseChoice</span>::<span class="ident">Dense</span>(<span class="macro">vec</span><span class="macro">!</span>[]))
        }
    }

    <span class="kw">fn</span> <span class="ident">goto</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">b1</span>: <span class="ident">u8</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span> {
        <span class="kw">match</span> <span class="self">self</span>.<span class="number">0</span> {
            <span class="ident">DenseChoice</span>::<span class="ident">Sparse</span>(<span class="kw-2">ref</span> <span class="ident">m</span>) <span class="op">=&gt;</span> <span class="ident">m</span>[<span class="ident">b1</span> <span class="kw">as</span> <span class="ident">usize</span>],
            <span class="ident">DenseChoice</span>::<span class="ident">Dense</span>(<span class="kw-2">ref</span> <span class="ident">m</span>) <span class="op">=&gt;</span> {
                <span class="kw">for</span> <span class="kw-2">&amp;</span>(<span class="ident">b2</span>, <span class="ident">si</span>) <span class="kw">in</span> <span class="ident">m</span> {
                    <span class="kw">if</span> <span class="ident">b1</span> <span class="op">==</span> <span class="ident">b2</span> {
                        <span class="kw">return</span> <span class="ident">si</span>;
                    }
                }
                <span class="ident">FAIL_STATE</span>
            }
        }
    }

    <span class="kw">fn</span> <span class="ident">set_goto</span>(<span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">b</span>: <span class="ident">u8</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>) {
        <span class="kw">match</span> <span class="self">self</span>.<span class="number">0</span> {
            <span class="ident">DenseChoice</span>::<span class="ident">Sparse</span>(<span class="kw-2">ref</span> <span class="kw-2">mut</span> <span class="ident">m</span>) <span class="op">=&gt;</span> <span class="ident">m</span>[<span class="ident">b</span> <span class="kw">as</span> <span class="ident">usize</span>] <span class="op">=</span> <span class="ident">si</span>,
            <span class="ident">DenseChoice</span>::<span class="ident">Dense</span>(<span class="kw-2">ref</span> <span class="kw-2">mut</span> <span class="ident">m</span>) <span class="op">=&gt;</span> <span class="ident">m</span>.<span class="ident">push</span>((<span class="ident">b</span>, <span class="ident">si</span>)),
        }
    }

    <span class="kw">fn</span> <span class="ident">heap_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span> {
        <span class="kw">match</span> <span class="self">self</span>.<span class="number">0</span> {
            <span class="ident">DenseChoice</span>::<span class="ident">Sparse</span>(<span class="kw-2">ref</span> <span class="ident">m</span>) <span class="op">=&gt;</span> <span class="ident">m</span>.<span class="ident">len</span>() <span class="op">*</span> <span class="number">4</span>,
            <span class="ident">DenseChoice</span>::<span class="ident">Dense</span>(<span class="kw-2">ref</span> <span class="ident">m</span>) <span class="op">=&gt;</span> <span class="ident">m</span>.<span class="ident">len</span>() <span class="op">*</span> (<span class="number">1</span> <span class="op">+</span> <span class="number">4</span>),
        }
    }
}

<span class="doccomment">/// State transitions that are always sparse.</span>
<span class="doccomment">///</span>
<span class="doccomment">/// This can use enormous amounts of memory when there are many patterns,</span>
<span class="doccomment">/// but matching is very fast.</span>
<span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>, <span class="ident">Debug</span>)]</span>
<span class="kw">pub</span> <span class="kw">struct</span> <span class="ident">Sparse</span>(<span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">StateIdx</span><span class="op">&gt;</span>);

<span class="kw">impl</span> <span class="ident">Transitions</span> <span class="kw">for</span> <span class="ident">Sparse</span> {
    <span class="kw">fn</span> <span class="ident">new</span>(_: <span class="ident">u32</span>) <span class="op">-&gt;</span> <span class="ident">Sparse</span> {
        <span class="ident">Sparse</span>(<span class="macro">vec</span><span class="macro">!</span>[<span class="number">0</span>; <span class="number">256</span>])
    }

    <span class="attribute">#[<span class="ident">inline</span>]</span>
    <span class="kw">fn</span> <span class="ident">goto</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">b</span>: <span class="ident">u8</span>) <span class="op">-&gt;</span> <span class="ident">StateIdx</span> {
        <span class="self">self</span>.<span class="number">0</span>[<span class="ident">b</span> <span class="kw">as</span> <span class="ident">usize</span>]
    }

    <span class="kw">fn</span> <span class="ident">set_goto</span>(<span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="self">self</span>, <span class="ident">b</span>: <span class="ident">u8</span>, <span class="ident">si</span>: <span class="ident">StateIdx</span>) {
        <span class="self">self</span>.<span class="number">0</span>[<span class="ident">b</span> <span class="kw">as</span> <span class="ident">usize</span>] <span class="op">=</span> <span class="ident">si</span>;
    }

    <span class="kw">fn</span> <span class="ident">heap_bytes</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">usize</span> {
        <span class="self">self</span>.<span class="number">0</span>.<span class="ident">len</span>() <span class="op">*</span> <span class="number">4</span>
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">S</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;&gt;</span> <span class="ident">FromIterator</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span> <span class="kw">for</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span> {
    <span class="doccomment">/// Create an automaton from an iterator of strings.</span>
    <span class="kw">fn</span> <span class="ident">from_iter</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span>(<span class="ident">it</span>: <span class="ident">T</span>) <span class="op">-&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span> <span class="kw">where</span> <span class="ident">T</span>: <span class="ident">IntoIterator</span><span class="op">&lt;</span><span class="ident">Item</span><span class="op">=</span><span class="ident">S</span><span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">it</span>)
    }
}

<span class="comment">// Provide some question debug impls for viewing automatons.</span>
<span class="comment">// The custom impls mostly exist for special showing of sparse maps.</span>

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">P</span>: <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> <span class="op">+</span> <span class="ident">fmt</span>::<span class="ident">Debug</span>, <span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span>
        <span class="ident">fmt</span>::<span class="ident">Debug</span> <span class="kw">for</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">P</span>, <span class="ident">T</span><span class="op">&gt;</span> {
    <span class="kw">fn</span> <span class="ident">fmt</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">f</span>: <span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="ident">fmt</span>::<span class="ident">Formatter</span>) <span class="op">-&gt;</span> <span class="ident">fmt</span>::<span class="prelude-ty">Result</span> {
        <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">iter</span>::<span class="ident">repeat</span>;

        <span class="macro">try</span><span class="macro">!</span>(<span class="macro">writeln</span><span class="macro">!</span>(<span class="ident">f</span>, <span class="string">&quot;{}&quot;</span>, <span class="ident">repeat</span>(<span class="string">&#39;-&#39;</span>).<span class="ident">take</span>(<span class="number">79</span>).<span class="ident">collect</span>::<span class="op">&lt;</span><span class="ident">String</span><span class="op">&gt;</span>()));
        <span class="macro">try</span><span class="macro">!</span>(<span class="macro">writeln</span><span class="macro">!</span>(<span class="ident">f</span>, <span class="string">&quot;Patterns: {:?}&quot;</span>, <span class="self">self</span>.<span class="ident">pats</span>));
        <span class="kw">for</span> (<span class="ident">i</span>, <span class="ident">state</span>) <span class="kw">in</span> <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">iter</span>().<span class="ident">enumerate</span>().<span class="ident">skip</span>(<span class="number">1</span>) {
            <span class="macro">try</span><span class="macro">!</span>(<span class="macro">writeln</span><span class="macro">!</span>(<span class="ident">f</span>, <span class="string">&quot;{:3}: {}&quot;</span>, <span class="ident">i</span>, <span class="ident">state</span>.<span class="ident">debug</span>(<span class="ident">i</span> <span class="op">==</span> <span class="number">1</span>)));
        }
        <span class="macro">write</span><span class="macro">!</span>(<span class="ident">f</span>, <span class="string">&quot;{}&quot;</span>, <span class="ident">repeat</span>(<span class="string">&#39;-&#39;</span>).<span class="ident">take</span>(<span class="number">79</span>).<span class="ident">collect</span>::<span class="op">&lt;</span><span class="ident">String</span><span class="op">&gt;</span>())
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="kw">fn</span> <span class="ident">debug</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">root</span>: <span class="ident">bool</span>) <span class="op">-&gt;</span> <span class="ident">String</span> {
        <span class="macro">format</span><span class="macro">!</span>(<span class="string">&quot;State {{ depth: {:?}, out: {:?}, fail: {:?}, goto: {{{}}} }}&quot;</span>,
                <span class="self">self</span>.<span class="ident">depth</span>, <span class="self">self</span>.<span class="ident">out</span>, <span class="self">self</span>.<span class="ident">fail</span>, <span class="self">self</span>.<span class="ident">goto_string</span>(<span class="ident">root</span>))
    }

    <span class="kw">fn</span> <span class="ident">goto_string</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">root</span>: <span class="ident">bool</span>) <span class="op">-&gt;</span> <span class="ident">String</span> {
        <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">char</span>::<span class="ident">from_u32</span>;

        <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">goto</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[];
        <span class="kw">for</span> <span class="ident">b</span> <span class="kw">in</span> (<span class="number">0</span>..<span class="number">256</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">b</span><span class="op">|</span> <span class="ident">b</span> <span class="kw">as</span> <span class="ident">u8</span>) {
            <span class="kw">let</span> <span class="ident">si</span> <span class="op">=</span> <span class="self">self</span>.<span class="ident">goto</span>(<span class="ident">b</span>);
            <span class="kw">if</span> (<span class="op">!</span><span class="ident">root</span> <span class="op">&amp;&amp;</span> <span class="ident">si</span> <span class="op">==</span> <span class="ident">FAIL_STATE</span>) <span class="op">||</span> (<span class="ident">root</span> <span class="op">&amp;&amp;</span> <span class="ident">si</span> <span class="op">==</span> <span class="ident">ROOT_STATE</span>) {
                <span class="kw">continue</span>;
            }
            <span class="ident">goto</span>.<span class="ident">push</span>(<span class="macro">format</span><span class="macro">!</span>(<span class="string">&quot;{} =&gt; {}&quot;</span>, <span class="ident">from_u32</span>(<span class="ident">b</span> <span class="kw">as</span> <span class="ident">u32</span>).<span class="ident">unwrap</span>(), <span class="ident">si</span>));
        }
        <span class="ident">goto</span>.<span class="ident">join</span>(<span class="string">&quot;, &quot;</span>)
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">fmt</span>::<span class="ident">Debug</span> <span class="kw">for</span> <span class="ident">State</span><span class="op">&lt;</span><span class="ident">T</span><span class="op">&gt;</span> {
    <span class="kw">fn</span> <span class="ident">fmt</span>(<span class="kw-2">&amp;</span><span class="self">self</span>, <span class="ident">f</span>: <span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="ident">fmt</span>::<span class="ident">Formatter</span>) <span class="op">-&gt;</span> <span class="ident">fmt</span>::<span class="prelude-ty">Result</span> {
        <span class="macro">write</span><span class="macro">!</span>(<span class="ident">f</span>, <span class="string">&quot;{}&quot;</span>, <span class="self">self</span>.<span class="ident">debug</span>(<span class="bool-val">false</span>))
    }
}

<span class="kw">impl</span><span class="op">&lt;</span><span class="ident">T</span>: <span class="ident">Transitions</span><span class="op">&gt;</span> <span class="ident">AcAutomaton</span><span class="op">&lt;</span><span class="ident">String</span>, <span class="ident">T</span><span class="op">&gt;</span> {
    <span class="attribute">#[<span class="ident">doc</span>(<span class="ident">hidden</span>)]</span>
    <span class="kw">pub</span> <span class="kw">fn</span> <span class="ident">dot</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">String</span> {
        <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">fmt</span>::<span class="ident">Write</span>;
        <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">out</span> <span class="op">=</span> <span class="ident">String</span>::<span class="ident">new</span>();
        <span class="macro">macro_rules</span><span class="macro">!</span> <span class="ident">w</span> {
            (<span class="macro-nonterminal">$</span><span class="macro-nonterminal">w</span>:<span class="ident">expr</span>, $(<span class="macro-nonterminal">$</span><span class="macro-nonterminal">tt</span>:<span class="ident">tt</span>)<span class="kw-2">*</span>) <span class="op">=&gt;</span> { {<span class="macro">write</span><span class="macro">!</span>(<span class="macro-nonterminal">$</span><span class="macro-nonterminal">w</span>, $(<span class="macro-nonterminal">$</span><span class="macro-nonterminal">tt</span>)<span class="kw-2">*</span>)}.<span class="ident">unwrap</span>() }
        }

        <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">r#&quot;
digraph automaton {{
    label=&lt;&lt;FONT POINT-SIZE=&quot;20&quot;&gt;{}&lt;/FONT&gt;&gt;;
    labelloc=&quot;l&quot;;
    labeljust=&quot;l&quot;;
    rankdir=&quot;LR&quot;;
&quot;#</span>, <span class="self">self</span>.<span class="ident">pats</span>.<span class="ident">join</span>(<span class="string">&quot;, &quot;</span>));
        <span class="kw">for</span> (<span class="ident">i</span>, <span class="ident">s</span>) <span class="kw">in</span> <span class="self">self</span>.<span class="ident">states</span>.<span class="ident">iter</span>().<span class="ident">enumerate</span>().<span class="ident">skip</span>(<span class="number">1</span>) {
            <span class="kw">let</span> <span class="ident">i</span> <span class="op">=</span> <span class="ident">i</span> <span class="kw">as</span> <span class="ident">u32</span>;
            <span class="kw">if</span> <span class="ident">s</span>.<span class="ident">out</span>.<span class="ident">len</span>() <span class="op">==</span> <span class="number">0</span> {
                <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">&quot;    {};\n&quot;</span>, <span class="ident">i</span>);
            } <span class="kw">else</span> {
                <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">&quot;    {} [peripheries=2];\n&quot;</span>, <span class="ident">i</span>);
            }
            <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">&quot;    {} -&gt; {} [style=dashed];\n&quot;</span>, <span class="ident">i</span>, <span class="ident">s</span>.<span class="ident">fail</span>);
            <span class="kw">for</span> <span class="ident">b</span> <span class="kw">in</span> (<span class="number">0</span>..<span class="number">256</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">b</span><span class="op">|</span> <span class="ident">b</span> <span class="kw">as</span> <span class="ident">u8</span>) {
                <span class="kw">let</span> <span class="ident">si</span> <span class="op">=</span> <span class="ident">s</span>.<span class="ident">goto</span>(<span class="ident">b</span>);
                <span class="kw">if</span> <span class="ident">si</span> <span class="op">==</span> <span class="ident">FAIL_STATE</span> <span class="op">||</span> (<span class="ident">i</span> <span class="op">==</span> <span class="ident">ROOT_STATE</span> <span class="op">&amp;&amp;</span> <span class="ident">si</span> <span class="op">==</span> <span class="ident">ROOT_STATE</span>) {
                    <span class="kw">continue</span>;
                }
                <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">&quot;    {} -&gt; {} [label={}];\n&quot;</span>, <span class="ident">i</span>, <span class="ident">si</span>, <span class="ident">b</span> <span class="kw">as</span> <span class="ident">char</span>);
            }
        }
        <span class="macro">w</span><span class="macro">!</span>(<span class="ident">out</span>, <span class="string">&quot;}}&quot;</span>);
        <span class="ident">out</span>
    }
}

<span class="kw">fn</span> <span class="ident">vec_bytes</span>() <span class="op">-&gt;</span> <span class="ident">usize</span> {
    <span class="ident">usize_bytes</span>() <span class="op">*</span> <span class="number">3</span>
}

<span class="kw">fn</span> <span class="ident">usize_bytes</span>() <span class="op">-&gt;</span> <span class="ident">usize</span> {
    <span class="kw">let</span> <span class="ident">bits</span> <span class="op">=</span> <span class="ident">usize</span>::<span class="ident">max_value</span>().<span class="ident">count_ones</span>() <span class="kw">as</span> <span class="ident">usize</span>;
    <span class="ident">bits</span> <span class="op">/</span> <span class="number">8</span>
}

<span class="attribute">#[<span class="ident">cfg</span>(<span class="ident">test</span>)]</span>
<span class="kw">mod</span> <span class="ident">tests</span> {
    <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">collections</span>::<span class="ident">HashSet</span>;
    <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">io</span>;

    <span class="kw">use</span> <span class="ident">quickcheck</span>::{<span class="ident">Arbitrary</span>, <span class="ident">Gen</span>, <span class="ident">quickcheck</span>};

    <span class="kw">use</span> <span class="kw">super</span>::{<span class="ident">Automaton</span>, <span class="ident">AcAutomaton</span>, <span class="ident">Match</span>};

    <span class="kw">fn</span> <span class="ident">aut_find</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>()).<span class="ident">find</span>(<span class="kw-2">&amp;</span><span class="ident">haystack</span>).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_finds</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="kw">let</span> <span class="ident">cur</span> <span class="op">=</span> <span class="ident">io</span>::<span class="ident">Cursor</span>::<span class="ident">new</span>(<span class="ident">haystack</span>.<span class="ident">as_bytes</span>());
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>())
            .<span class="ident">stream_find</span>(<span class="ident">cur</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">r</span><span class="op">|</span> <span class="ident">r</span>.<span class="ident">unwrap</span>()).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findf</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>()).<span class="ident">into_full</span>().<span class="ident">find</span>(<span class="ident">haystack</span>).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findfs</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="kw">let</span> <span class="ident">cur</span> <span class="op">=</span> <span class="ident">io</span>::<span class="ident">Cursor</span>::<span class="ident">new</span>(<span class="ident">haystack</span>.<span class="ident">as_bytes</span>());
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>())
            .<span class="ident">into_full</span>()
            .<span class="ident">stream_find</span>(<span class="ident">cur</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">r</span><span class="op">|</span> <span class="ident">r</span>.<span class="ident">unwrap</span>()).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findo</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>()).<span class="ident">find_overlapping</span>(<span class="ident">haystack</span>).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findos</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="kw">let</span> <span class="ident">cur</span> <span class="op">=</span> <span class="ident">io</span>::<span class="ident">Cursor</span>::<span class="ident">new</span>(<span class="ident">haystack</span>.<span class="ident">as_bytes</span>());
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>())
            .<span class="ident">stream_find_overlapping</span>(<span class="ident">cur</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">r</span><span class="op">|</span> <span class="ident">r</span>.<span class="ident">unwrap</span>()).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findfo</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>())
            .<span class="ident">into_full</span>().<span class="ident">find_overlapping</span>(<span class="ident">haystack</span>).<span class="ident">collect</span>()
    }

    <span class="kw">fn</span> <span class="ident">aut_findfos</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> {
        <span class="kw">let</span> <span class="ident">cur</span> <span class="op">=</span> <span class="ident">io</span>::<span class="ident">Cursor</span>::<span class="ident">new</span>(<span class="ident">haystack</span>.<span class="ident">as_bytes</span>());
        <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="ident">xs</span>.<span class="ident">to_vec</span>())
            .<span class="ident">into_full</span>()
            .<span class="ident">stream_find_overlapping</span>(<span class="ident">cur</span>).<span class="ident">map</span>(<span class="op">|</span><span class="ident">r</span><span class="op">|</span> <span class="ident">r</span>.<span class="ident">unwrap</span>()).<span class="ident">collect</span>()
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">one_pattern_one_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;a&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;za&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">1</span>, <span class="ident">end</span>: <span class="number">2</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">one_pattern_many_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;a&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazazzzza&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">1</span>, <span class="ident">end</span>: <span class="number">2</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">4</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">8</span>, <span class="ident">end</span>: <span class="number">9</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">one_longer_pattern_one_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazabcz&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[ <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> } ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">one_longer_pattern_many_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazabczzzzazzzabc&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">14</span>, <span class="ident">end</span>: <span class="number">17</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_pattern_one_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;a&quot;</span>, <span class="string">&quot;b&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zb&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[ <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">1</span>, <span class="ident">end</span>: <span class="number">2</span> } ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_pattern_many_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;a&quot;</span>, <span class="string">&quot;b&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zbzazzzzb&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">1</span>, <span class="ident">end</span>: <span class="number">2</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">4</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">8</span>, <span class="ident">end</span>: <span class="number">9</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_one_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;xyz&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazxyzz&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[ <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> } ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_many_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;xyz&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazxyzzzzzazzzabcxyz&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">14</span>, <span class="ident">end</span>: <span class="number">17</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">17</span>, <span class="ident">end</span>: <span class="number">20</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_find</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_finds</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findf</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfs</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_overlap_one_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;bc&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zazabcz&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">4</span>, <span class="ident">end</span>: <span class="number">6</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_overlap_one_match_reverse</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;bc&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;xbc&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[ <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">1</span>, <span class="ident">end</span>: <span class="number">3</span> } ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_overlap_many_match</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;bc&quot;</span>, <span class="string">&quot;c&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zzzabczzzbczzzc&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">4</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">5</span>, <span class="ident">end</span>: <span class="number">6</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">9</span>, <span class="ident">end</span>: <span class="number">11</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">10</span>, <span class="ident">end</span>: <span class="number">11</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">14</span>, <span class="ident">end</span>: <span class="number">15</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">many_longer_pattern_overlap_many_match_reverse</span>() {
        <span class="kw">let</span> <span class="ident">ns</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;abc&quot;</span>, <span class="string">&quot;bc&quot;</span>, <span class="string">&quot;c&quot;</span>];
        <span class="kw">let</span> <span class="ident">hay</span> <span class="op">=</span> <span class="string">&quot;zzzczzzbczzzabc&quot;</span>;
        <span class="kw">let</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">3</span>, <span class="ident">end</span>: <span class="number">4</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">7</span>, <span class="ident">end</span>: <span class="number">9</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">8</span>, <span class="ident">end</span>: <span class="number">9</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">0</span>, <span class="ident">start</span>: <span class="number">12</span>, <span class="ident">end</span>: <span class="number">15</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">1</span>, <span class="ident">start</span>: <span class="number">13</span>, <span class="ident">end</span>: <span class="number">15</span> },
            <span class="ident">Match</span> { <span class="ident">pati</span>: <span class="number">2</span>, <span class="ident">start</span>: <span class="number">14</span>, <span class="ident">end</span>: <span class="number">15</span> },
        ];
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfo</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="kw-2">&amp;</span><span class="ident">aut_findfos</span>(<span class="kw-2">&amp;</span><span class="ident">ns</span>, <span class="ident">hay</span>), <span class="kw-2">&amp;</span><span class="ident">matches</span>);
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">pattern_returns_original_type</span>() {
        <span class="kw">let</span> <span class="ident">aut</span> <span class="op">=</span> <span class="ident">AcAutomaton</span>::<span class="ident">new</span>(<span class="macro">vec</span><span class="macro">!</span>[<span class="string">&quot;apple&quot;</span>, <span class="string">&quot;maple&quot;</span>]);

        <span class="comment">// Explicitly given this type to assert that the thing returned</span>
        <span class="comment">// from the function is our original type.</span>
        <span class="kw">let</span> <span class="ident">pat</span>: <span class="kw-2">&amp;</span><span class="ident">str</span> <span class="op">=</span> <span class="ident">aut</span>.<span class="ident">pattern</span>(<span class="number">0</span>);
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="ident">pat</span>, <span class="string">&quot;apple&quot;</span>);

        <span class="comment">// Also check the return type of the `patterns` function.</span>
        <span class="kw">let</span> <span class="ident">pats</span>: <span class="kw-2">&amp;</span>[<span class="kw-2">&amp;</span><span class="ident">str</span>] <span class="op">=</span> <span class="ident">aut</span>.<span class="ident">patterns</span>();
        <span class="macro">assert_eq</span><span class="macro">!</span>(<span class="ident">pats</span>, <span class="kw-2">&amp;</span>[<span class="string">&quot;apple&quot;</span>, <span class="string">&quot;maple&quot;</span>]);
    }

    <span class="comment">// Quickcheck time.</span>

    <span class="comment">// This generates very small ascii strings, which makes them more likely</span>
    <span class="comment">// to interact in interesting ways with larger haystack strings.</span>
    <span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>, <span class="ident">Debug</span>, <span class="ident">PartialEq</span>, <span class="ident">Eq</span>, <span class="ident">PartialOrd</span>, <span class="ident">Ord</span>)]</span>
    <span class="kw">pub</span> <span class="kw">struct</span> <span class="ident">SmallAscii</span>(<span class="ident">String</span>);

    <span class="kw">impl</span> <span class="ident">Arbitrary</span> <span class="kw">for</span> <span class="ident">SmallAscii</span> {
        <span class="kw">fn</span> <span class="ident">arbitrary</span><span class="op">&lt;</span><span class="ident">G</span>: <span class="ident">Gen</span><span class="op">&gt;</span>(<span class="ident">g</span>: <span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="ident">G</span>) <span class="op">-&gt;</span> <span class="ident">SmallAscii</span> {
            <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">char</span>::<span class="ident">from_u32</span>;
            <span class="ident">SmallAscii</span>((<span class="number">0</span>..<span class="number">2</span>)
                       .<span class="ident">map</span>(<span class="op">|</span>_<span class="op">|</span> <span class="ident">from_u32</span>(<span class="ident">g</span>.<span class="ident">gen_range</span>(<span class="number">97</span>, <span class="number">123</span>)).<span class="ident">unwrap</span>())
                       .<span class="ident">collect</span>())
        }

        <span class="kw">fn</span> <span class="ident">shrink</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">Box</span><span class="op">&lt;</span><span class="ident">Iterator</span><span class="op">&lt;</span><span class="ident">Item</span><span class="op">=</span><span class="ident">SmallAscii</span><span class="op">&gt;&gt;</span> {
            <span class="ident">Box</span>::<span class="ident">new</span>(<span class="self">self</span>.<span class="number">0</span>.<span class="ident">shrink</span>().<span class="ident">map</span>(<span class="ident">SmallAscii</span>))
        }
    }

    <span class="kw">impl</span> <span class="ident">From</span><span class="op">&lt;</span><span class="ident">SmallAscii</span><span class="op">&gt;</span> <span class="kw">for</span> <span class="ident">String</span> {
        <span class="kw">fn</span> <span class="ident">from</span>(<span class="ident">s</span>: <span class="ident">SmallAscii</span>) <span class="op">-&gt;</span> <span class="ident">String</span> { <span class="ident">s</span>.<span class="number">0</span> }
    }

    <span class="kw">impl</span> <span class="ident">AsRef</span><span class="op">&lt;</span>[<span class="ident">u8</span>]<span class="op">&gt;</span> <span class="kw">for</span> <span class="ident">SmallAscii</span> {
        <span class="kw">fn</span> <span class="ident">as_ref</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="kw-2">&amp;</span>[<span class="ident">u8</span>] { <span class="self">self</span>.<span class="number">0</span>.<span class="ident">as_ref</span>() }
    }

    <span class="comment">// This is the same arbitrary impl as `String`, except it has a bias toward</span>
    <span class="comment">// ASCII characters.</span>
    <span class="attribute">#[<span class="ident">derive</span>(<span class="ident">Clone</span>, <span class="ident">Debug</span>, <span class="ident">PartialEq</span>, <span class="ident">Eq</span>, <span class="ident">PartialOrd</span>, <span class="ident">Ord</span>)]</span>
    <span class="kw">pub</span> <span class="kw">struct</span> <span class="ident">BiasAscii</span>(<span class="ident">String</span>);

    <span class="kw">impl</span> <span class="ident">Arbitrary</span> <span class="kw">for</span> <span class="ident">BiasAscii</span> {
        <span class="kw">fn</span> <span class="ident">arbitrary</span><span class="op">&lt;</span><span class="ident">G</span>: <span class="ident">Gen</span><span class="op">&gt;</span>(<span class="ident">g</span>: <span class="kw-2">&amp;</span><span class="kw-2">mut</span> <span class="ident">G</span>) <span class="op">-&gt;</span> <span class="ident">BiasAscii</span> {
            <span class="kw">use</span> <span class="ident">std</span>::<span class="ident">char</span>::<span class="ident">from_u32</span>;
            <span class="kw">let</span> <span class="ident">size</span> <span class="op">=</span> { <span class="kw">let</span> <span class="ident">s</span> <span class="op">=</span> <span class="ident">g</span>.<span class="ident">size</span>(); <span class="ident">g</span>.<span class="ident">gen_range</span>(<span class="number">0</span>, <span class="ident">s</span>) };
            <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">s</span> <span class="op">=</span> <span class="ident">String</span>::<span class="ident">with_capacity</span>(<span class="ident">size</span>);
            <span class="kw">for</span> _ <span class="kw">in</span> <span class="number">0</span>..<span class="ident">size</span> {
                <span class="kw">if</span> <span class="ident">g</span>.<span class="ident">gen_weighted_bool</span>(<span class="number">3</span>) {
                    <span class="ident">s</span>.<span class="ident">push</span>(<span class="ident">char</span>::<span class="ident">arbitrary</span>(<span class="ident">g</span>));
                } <span class="kw">else</span> {
                    <span class="kw">for</span> _ <span class="kw">in</span> <span class="number">0</span>..<span class="number">5</span> {
                        <span class="ident">s</span>.<span class="ident">push</span>(<span class="ident">from_u32</span>(<span class="ident">g</span>.<span class="ident">gen_range</span>(<span class="number">97</span>, <span class="number">123</span>)).<span class="ident">unwrap</span>());
                    }
                }
            }
            <span class="ident">BiasAscii</span>(<span class="ident">s</span>)
        }

        <span class="kw">fn</span> <span class="ident">shrink</span>(<span class="kw-2">&amp;</span><span class="self">self</span>) <span class="op">-&gt;</span> <span class="ident">Box</span><span class="op">&lt;</span><span class="ident">Iterator</span><span class="op">&lt;</span><span class="ident">Item</span><span class="op">=</span><span class="ident">BiasAscii</span><span class="op">&gt;&gt;</span> {
            <span class="ident">Box</span>::<span class="ident">new</span>(<span class="self">self</span>.<span class="number">0</span>.<span class="ident">shrink</span>().<span class="ident">map</span>(<span class="ident">BiasAscii</span>))
        }
    }

    <span class="kw">fn</span> <span class="ident">naive_find</span><span class="op">&lt;</span><span class="ident">S</span><span class="op">&gt;</span>(<span class="ident">xs</span>: <span class="kw-2">&amp;</span>[<span class="ident">S</span>], <span class="ident">haystack</span>: <span class="kw-2">&amp;</span><span class="ident">str</span>) <span class="op">-&gt;</span> <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span>
            <span class="kw">where</span> <span class="ident">S</span>: <span class="ident">Clone</span> <span class="op">+</span> <span class="ident">Into</span><span class="op">&lt;</span><span class="ident">String</span><span class="op">&gt;</span> {
        <span class="kw">let</span> <span class="ident">needles</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">String</span><span class="op">&gt;</span> <span class="op">=</span>
            <span class="ident">xs</span>.<span class="ident">to_vec</span>().<span class="ident">into_iter</span>().<span class="ident">map</span>(<span class="ident">Into</span>::<span class="ident">into</span>).<span class="ident">collect</span>();
        <span class="kw">let</span> <span class="kw-2">mut</span> <span class="ident">matches</span> <span class="op">=</span> <span class="macro">vec</span><span class="macro">!</span>[];
        <span class="kw">for</span> <span class="ident">hi</span> <span class="kw">in</span> <span class="number">0</span>..<span class="ident">haystack</span>.<span class="ident">len</span>() {
            <span class="kw">for</span> (<span class="ident">pati</span>, <span class="ident">needle</span>) <span class="kw">in</span> <span class="ident">needles</span>.<span class="ident">iter</span>().<span class="ident">enumerate</span>() {
                <span class="kw">let</span> <span class="ident">needle</span> <span class="op">=</span> <span class="ident">needle</span>.<span class="ident">as_bytes</span>();
                <span class="kw">if</span> <span class="ident">needle</span>.<span class="ident">len</span>() <span class="op">==</span> <span class="number">0</span> <span class="op">||</span> <span class="ident">needle</span>.<span class="ident">len</span>() <span class="op">&gt;</span> <span class="ident">haystack</span>.<span class="ident">len</span>() <span class="op">-</span> <span class="ident">hi</span> {
                    <span class="kw">continue</span>;
                }
                <span class="kw">if</span> <span class="ident">needle</span> <span class="op">==</span> <span class="kw-2">&amp;</span><span class="ident">haystack</span>.<span class="ident">as_bytes</span>()[<span class="ident">hi</span>..<span class="ident">hi</span><span class="op">+</span><span class="ident">needle</span>.<span class="ident">len</span>()] {
                    <span class="ident">matches</span>.<span class="ident">push</span>(<span class="ident">Match</span> {
                        <span class="ident">pati</span>: <span class="ident">pati</span>,
                        <span class="ident">start</span>: <span class="ident">hi</span>,
                        <span class="ident">end</span>: <span class="ident">hi</span> <span class="op">+</span> <span class="ident">needle</span>.<span class="ident">len</span>(),
                    });
                }
            }
        }
        <span class="ident">matches</span>
    }

    <span class="attribute">#[<span class="ident">test</span>]</span>
    <span class="kw">fn</span> <span class="ident">qc_ac_equals_naive</span>() {
        <span class="kw">fn</span> <span class="ident">prop</span>(<span class="ident">needles</span>: <span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">SmallAscii</span><span class="op">&gt;</span>, <span class="ident">haystack</span>: <span class="ident">BiasAscii</span>) <span class="op">-&gt;</span> <span class="ident">bool</span> {
            <span class="kw">let</span> <span class="ident">aut_matches</span> <span class="op">=</span> <span class="ident">aut_findo</span>(<span class="kw-2">&amp;</span><span class="ident">needles</span>, <span class="kw-2">&amp;</span><span class="ident">haystack</span>.<span class="number">0</span>);
            <span class="kw">let</span> <span class="ident">naive_matches</span> <span class="op">=</span> <span class="ident">naive_find</span>(<span class="kw-2">&amp;</span><span class="ident">needles</span>, <span class="kw-2">&amp;</span><span class="ident">haystack</span>.<span class="number">0</span>);
            <span class="comment">// Ordering isn&#39;t always the same. I don&#39;t think we care, so do</span>
            <span class="comment">// an unordered comparison.</span>
            <span class="kw">let</span> <span class="ident">aset</span>: <span class="ident">HashSet</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span> <span class="op">=</span> <span class="ident">aut_matches</span>.<span class="ident">iter</span>().<span class="ident">cloned</span>().<span class="ident">collect</span>();
            <span class="kw">let</span> <span class="ident">nset</span>: <span class="ident">HashSet</span><span class="op">&lt;</span><span class="ident">Match</span><span class="op">&gt;</span> <span class="op">=</span> <span class="ident">naive_matches</span>.<span class="ident">iter</span>().<span class="ident">cloned</span>().<span class="ident">collect</span>();
            <span class="ident">aset</span> <span class="op">==</span> <span class="ident">nset</span>
        }
        <span class="ident">quickcheck</span>(<span class="ident">prop</span> <span class="kw">as</span> <span class="kw">fn</span>(<span class="ident">Vec</span><span class="op">&lt;</span><span class="ident">SmallAscii</span><span class="op">&gt;</span>, <span class="ident">BiasAscii</span>) <span class="op">-&gt;</span> <span class="ident">bool</span>);
    }
}
</pre>
</section>
    <section id='search' class="content hidden"></section>

    <section class="footer"></section>

    <aside id="help" class="hidden">
        <div>
            <h1 class="hidden">Help</h1>

            <div class="shortcuts">
                <h2>Keyboard Shortcuts</h2>

                <dl>
                    <dt>?</dt>
                    <dd>Show this help dialog</dd>
                    <dt>S</dt>
                    <dd>Focus the search field</dd>
                    <dt>&larrb;</dt>
                    <dd>Move up in search results</dd>
                    <dt>&rarrb;</dt>
                    <dd>Move down in search results</dd>
                    <dt>&#9166;</dt>
                    <dd>Go to active search result</dd>
                    <dt>+</dt>
                    <dd>Collapse/expand all sections</dd>
                </dl>
            </div>

            <div class="infos">
                <h2>Search Tricks</h2>

                <p>
                    Prefix searches with a type followed by a colon (e.g.
                    <code>fn:</code>) to restrict the search to a given type.
                </p>

                <p>
                    Accepted types are: <code>fn</code>, <code>mod</code>,
                    <code>struct</code>, <code>enum</code>,
                    <code>trait</code>, <code>type</code>, <code>macro</code>,
                    and <code>const</code>.
                </p>

                <p>
                    Search functions by type signature (e.g.
                    <code>vec -> usize</code> or <code>* -> vec</code>)
                </p>
            </div>
        </div>
    </aside>

    

    <script>
        window.rootPath = "../../";
        window.currentCrate = "aho_corasick";
    </script>
    <script src="../../main.js"></script>
    <script defer src="../../search-index.js"></script>
</body>
</html>